package tiruvury.InterviewPrep.DataStructures;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.List;

import tiruvury.InterviewPrep.HelperClasses.MaxSumSubarray;

public class MyArrays
{
	/*
	 * REMEMBER LOGIC!!
	 */
	public static int[] DutchNationalFlagSort(int[] arr)
	{
		if (arr == null || arr.length == 1)
		{
			return null;
		}

		int lo = 0; // points to the first 1
		int cur = 0;
		int hi = arr.length - 1;

		while (cur <= hi)
		{
			if (arr[cur] == 0)
			{
				arr = swap(arr, cur, lo);
				lo++;
				cur++;
			}
			else if (arr[cur] == 2)
			{
				arr = swap(arr, cur, hi);
				hi--;
			}
			else
			{
				cur++;
			}
		}

		return arr;
	}

	private static int[] swap(int[] arr, int i, int j)
	{
		int temp;
		if (arr != null && i >= 0 && j < arr.length)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}

		return arr;
	}

	public static void PrintPairs(int[] arr, int sum)
	{
		if (arr == null || arr.length == 1)
		{
			return;
		}

		Hashtable<Integer, Integer> ht = new Hashtable<Integer, Integer>();

		/* Construct Hashtable with numbers and counts */
		for (int i = 0; i < arr.length; i++)
		{
			if (ht.containsKey(arr[i]))
			{
				ht.put(arr[i], ht.get(arr[i]) + 1);
			}
			else
			{
				ht.put(arr[i], 1);
			}
		}

		int complement;
		int numCount;
		int complementCount;
		System.out.println("Printing Pairs: ");
		/*
		 * SYNTAXERROR: To iterate over keys in a hashtable, use ht.keySet()
		 */
		for (int num : ht.keySet())
		{
			complement = sum - num;

			if (ht.containsKey(complement))
			{
				complementCount = ht.get(complement);
				numCount = ht.get(num);
				PrintPair(num, complement, numCount, complementCount);
			}
		}
	}

	private static void PrintPair(int num1, int num2, int count1, int count2)
	{
		for (int i = 0; i < count1; i++)
		{
			for (int j = 0; j < count2; j++)
			{
				System.out.print(" Pair: {" + num1 + ", " + num2 + "},");
			}
		}
	}

	public static int[] GenerateRandomIntArray(int size, int rangeMin, int rangeMax, boolean returnSortedArray)
	{
		if (size <= 0)
			return new int[0];

		int[] arr = new int[size];

		// Generate Array
		for (int i = 0; i < size; i++)
		{
			/*
			 * REVIEW: This is how you generate a random number within a range
			 */
			arr[i] = rangeMin + (int) (Math.random() * (rangeMax - rangeMin + 1));
		}

		// Sort Array if needed
		if (returnSortedArray)
		{
			Arrays.sort(arr);
		}

		// Print Array
		System.out.print("The input array is: {");
		for (int i = 0; i < size; i++)
		{
			System.out.print(arr[i] + ", ");
		}
		System.out.println("}");

		return arr;
	}

	/**
	 * Return m random numbers in a given array
	 */
	public static void ReturnMRandNums(int[] arr, int m)
	{
		int n = arr.length;

		if (n > 0 && m > 0 && m <= n)
		{
			int randIdx = -1;
			int maxIdx = n - 1;
			int temp = 0;

			System.out.print(m + " random number(s) are: {");
			for (int i = 0; i < m; i++)
			{
				randIdx = (int) (Math.random() * (maxIdx + 1));
				temp = arr[randIdx];
				arr[randIdx] = arr[maxIdx];
				arr[maxIdx] = temp;
				System.out.print(arr[maxIdx] + ", ");
				maxIdx--;
			}
			System.out.print("}");

		}
	}

	public static MaxSumSubarray GetMaximumSumSubarray(int[] arr)
	{
		MaxSumSubarray maxSoFar = new MaxSumSubarray(0, 0, 0);
		MaxSumSubarray maxEndingHere = new MaxSumSubarray(0, 0, 0);

		for (int i = 0; i < arr.length; i++)
		{
			maxEndingHere.sum = maxEndingHere.sum + arr[i];
			maxEndingHere.highIdx = i;
			if (maxEndingHere.sum < 0)
			{
				maxEndingHere.sum = 0;
				maxEndingHere.lowIdx = maxEndingHere.highIdx = i + 1;
			}

			if (maxSoFar.sum < maxEndingHere.sum)
			{
				maxSoFar.sum = maxEndingHere.sum;
				maxSoFar.lowIdx = maxEndingHere.lowIdx;
				maxSoFar.highIdx = maxEndingHere.highIdx;
			}
		}

		return maxSoFar;
	}

	public static int FindMinInRotatedArray(int[] arr)
	{
		int low = 0;
		int high = arr.length - 1;
		int mid = (low + high) / 2;
		int min = 0;

		while (low < high)
		{
			if (arr[low] < arr[high])
			{
				min = arr[low];
				break;
			}
			else if (arr[low] > arr[mid])
			{
				high = mid;
			}
			else
			{
				low = mid + 1;
			}

			mid = (low + high) / 2;
		}

		if (low == high)
		{
			min = arr[low];
		}

		return min;
	}

	public static int FindIdxInRotatedArray(int[] rotArr, int num)
	{
		int low = 0;
		int high = rotArr.length - 1;
		int mid = -1;

		while (low <= high)
		{
			if (low == high)
			{
				if (num == rotArr[low])
				{
					return low;
				}
				break;
			}
			else
			{
				mid = (low + high) / 2;
				if (num == rotArr[mid])
				{
					return mid;
				}
				else if (num > rotArr[mid])
				{
					if (num > rotArr[high])
					{
						// Num in left half
						high = mid - 1;
					}
					else
					{
						// Num in right half
						low = mid + 1;
					}
				}
				else
				{
					if (num < rotArr[low])
					{
						// Num in right half
						low = mid + 1;
					}
					else
					{
						// Num in left half
						high = mid - 1;
					}
				}
			}
		}

		return -1;
	}

	public static int FindMagicIndex(int[] A, int low, int high)
	{
		if (low <= high)
		{
			int mid = (low + high) / 2;

			if (A[mid] == mid)
			{
				return mid;
			}
			else if (A[mid] > mid)
			{
				return FindMagicIndex(A, low, mid - 1);
			}
			else
			{
				return FindMagicIndex(A, mid + 1, high);
			}
		}

		return -1;
	}

	public static int[] MergeSort(int[] arr, int low, int high)
	{
		int[] mergedArr = null;
		if (low == high)
		{
			mergedArr = new int[1];
			mergedArr[0] = arr[low];
		}
		else if (low < high)
		{
			int mid = (low + high) / 2;
			int[] leftArr = MergeSort(arr, low, mid);
			int[] rightArr = MergeSort(arr, mid + 1, high);
			mergedArr = Merge(leftArr, rightArr);
		}

		return mergedArr;
	}

	private static int[] Merge(int[] leftArr, int[] rightArr)
	{
		List<Integer> mergedList = new ArrayList<Integer>();

		if (leftArr == null && rightArr == null)
		{
			return null;
		}
		else if (leftArr == null)
		{
			return rightArr;
		}
		else if (rightArr == null)
		{
			return leftArr;
		}

		int i = 0;
		int j = 0;
		int duplicateVal;
		while (true)
		{
			if (i < leftArr.length && j < rightArr.length)
			{
				if (leftArr[i] < rightArr[j])
				{
					mergedList.add(leftArr[i]);
					i++;
				}
				else if (leftArr[i] > rightArr[j])
				{
					mergedList.add(rightArr[j]);
					j++;
				}
				else
				{
					// Duplicate found
					duplicateVal = leftArr[i];
					mergedList.add(duplicateVal);
					i++;
					j++;
				}
			}
			else if (i < leftArr.length)
			{
				mergedList.add(leftArr[i]);
				i++;
			}
			else if (j < rightArr.length)
			{
				mergedList.add(rightArr[j]);
				j++;
			}
			else
			{
				// We've reached the end of both left and right arrays.
				break;
			}
		}

		/*
		 * SYNTAX ERROR: make the mergedarray a LIST. Cos you dont know the
		 * final size as left and right arrays may have duplicates.
		 * If you initialize mergedArray to sum of lengths of left and right
		 * arrays, you might end up with 0s for the unfilled indices (cos of
		 * duplicates).
		 */
		int[] mergedArr = new int[mergedList.size()];
		for (i = 0; i < mergedList.size(); i++)
		{
			mergedArr[i] = mergedList.get(i);
		}

		return mergedArr;

	}

	public static int[] rotateArrayByK(int[] arr, int k)
	{
		if (arr == null || k < 0 || k >= arr.length)
		{
			return null;
		}

		// First rotate entire number
		arr = rotateArray(arr, 0, arr.length - 1);

		// Rotate 0 through k -1
		arr = rotateArray(arr, 0, k - 1);

		// Rotate k through end
		arr = rotateArray(arr, k, arr.length - 1);

		return arr;
	}

	private static int[] rotateArray(int[] arr, int minIdx, int maxIdx)
	{
		int i = minIdx;
		int j = maxIdx;

		int temp;
		while (i < j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i++;
			j--;
		}

		return arr;
	}

	public static void PrintFibonacciNums(int n)
	{
		if (n < 0)
			return;

		int[] arr = new int[n + 1];
		for (int i = 0; i <= n; i++)
		{
			arr[i] = -1;
		}
		System.out.println("Printing fib nos");
		printFib(n, arr);
	}

	private static int printFib(int n, int[] arr)
	{
		if (arr[n] != -1)
		{
			return arr[n];
		}
		else if (n == 0)
		{
			arr[0] = 0;
		}
		else if (n == 1)
		{
			arr[1] = 1;
		}
		else
		{
			arr[n] = printFib(n - 1, arr) + printFib(n - 2, arr);
		}

		System.out.println(arr[n] + ", ");
		return arr[n];
	}
}
